package com.zjsru.plan2023.other;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: CookLee
 * @Date: 2023/7/1
 *  可被 5 整除的二进制前缀
 * 输入：nums = [0,1,1]
 * 输出：[true,false,false]
 * 解释：
 * 输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为 true 。
 *
 */
public class PrefixesDivBy5 {
    
    /**
     * 临时前缀和
     */
    private static int temp = 0;
    
    /**
     * 模拟
     *
     * @return {@link List}<{@link Boolean}>
     */
    public List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> booleans = new ArrayList<>();
        for (int num : nums) {
            booleans.add(this.helper(num));
        }
        return booleans;
    }
    
    /**
     * helper 判断是否能被5整除 助手类
     *
     * @helper num
     * @return {@link Boolean}
     */
    private Boolean helper(Integer num) {
        //temp<<1 位运算 为了在二进制表示上将其乘以 2。
        //由于每个位置上的元素只有 0 和 1 两种可能性，因此将前缀左移一位后，可以将当前位置的元素加到前缀上，以构建下一个前缀。
        //即是左移后的前缀与当前元素相加，得到下一个前缀的值。
        temp = (((temp << 1) + num) % 5);
        return temp == 0;
    }
    
    public static void main(String[] args) {
        PrefixesDivBy5 prefixesDivBy5 = new PrefixesDivBy5();
        int[] nums = new int[] {1,1,1};
        System.out.println(prefixesDivBy5.prefixesDivBy5(nums));
    }
}
